package seqlist.leetcode;

//反转链表(回文)
public class Num206_reverseList {
    //方法1 头插
    public ListNode reverseList(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode dummyHead=new ListNode(-1);
        while (head!=null){
            ListNode node=new ListNode(head.val);
            node.next=dummyHead.next;
            dummyHead.next=node;
            head=head.next;
        }
        return dummyHead.next;
    }

    //方法2 原地移动
    public ListNode reverseList2(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode prev=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode node=cur.next;
            cur.next=prev;
            prev=cur;
            cur=node;
        }
        return prev;
    }
    //方法3 递归
    public ListNode reverseList3(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode sec=head.next;
        ListNode newHead=reverseList3(head.next);
        sec.next=head;
        head.next=null;
        return newHead;
    }
}
